package primary;

import Utils.SortUtils;

/**
 * 插入排序算法(与整理牌的方法类似，一张张整理，将每张牌(即数组中的每个数)插入到已经有序的牌中的适当位置)
 * 平均情况下需要 N^2/4次比较以及 N^2/4次交换
 * 最坏情况是逆序数组
 * 最好情况是排好的数组(需要 N-1次比较和 0次交换)
 * @author xiaolu
 * @version 1.0
 * @date 2020/6/1 14:34
 */
public class Insertion {

    public static void sort(Comparable[] a){

        int N = a.length;
        for (int i = 1; i < N; i++) {
            // 取相同下标数的值，让它与它下标之前的值依次相比较，但下标要>0，若比之前的小，则交换位置
            for (int j = i; j > 0 && SortUtils.less(a[j], a[j-1]); j--) {
                SortUtils.exch(a, j, j-1);
            }
        }
    }

    public static void main(String[] args) {

        // 测试排序算法
        Integer[] a = {4, 23, 6, 78, 1, 54, 231, 9, 12};
        // Integer[] a = {1, 5, 6, 4, 343, 234};
        sort(a);
        assert SortUtils.isSorted(a);
        SortUtils.show(a);
    }
}
